import numpy as np
import os
import sys
from Bio.Cluster import kcluster
import time
sys.path.append(os.path.dirname(os.path.dirname(os.path.abspath(__file__)))+"/util")
from Util import AlgorithmUtil

class FPTD_Kmeans:
    # 构造函数
    def __init__(self, trajectory=[]):
        # 轨迹数据处理为list
        if(isinstance(trajectory,np.ndarray)):
            self.trajectory=trajectory.tolist()
        else:
            self.trajectory=trajectory
    
    # 获得合适的k值
    @staticmethod
    def getKValue(directionList):
        clustersNumber=0
        distributionList=[0,0,0,0,0,0,0,0]
        for direction in directionList:
            if 337.5 <= direction < 360 or 0 <= direction < 22.5:
                distributionList[0]=distributionList[0]+1
            elif 22.5<= direction < 67.5:
                distributionList[1]=distributionList[1]+1
            elif 67.5 <= direction < 112.5:
                distributionList[2]=distributionList[2]+1
            elif 112.5 <= direction < 157.5:
                distributionList[3]=distributionList[3]+1
            elif 157.5 <= direction < 202.5:
                distributionList[4]=distributionList[4]+1
            elif 202.5 <= direction < 247.5:
                distributionList[5]=distributionList[5]+1
            elif 247.5 <= direction < 292.5:
                distributionList[6]=distributionList[6]+1
            elif 292.5 <= direction < 337.5:
                distributionList[7]=distributionList[7]+1
        for distribution in distributionList:
            if distribution>0:
                clustersNumber=clustersNumber+1
        if clustersNumber==1:
            clustersNumber=2
        return clustersNumber
    # 获取潜在的轨迹分段索引序列（左开右闭）
    @staticmethod
    def getPotentialSegmentIndex(clusterLabels):
        indexList=[]
        # 遍历类簇标签序列
        for index,label in enumerate(clusterLabels):
        # 循环结束
            if index==len(clusterLabels)-1:
                break
            else:
                # 判断当前类簇标签是否与下一类簇标签一致
                if label!=clusterLabels[index+1]:
                   indexList.append(index)
        return indexList
    # 计算当前方向向量与所属类簇的内聚程度以及其与相邻子轨迹平均方向的分离程度
    @staticmethod
    def __calculate_C_S2(clusterSamples,currentSample,preSamples=None,nextSamples=None,isSame=False):
        # ------计算内聚度------
        cohesion = 0
        for sample in clusterSamples:
            # 如果相同
            if sample[0] == currentSample[0] and sample[1] == currentSample[1]:
                continue
            d, a = AlgorithmUtil.cosinDistance(sample, currentSample)
            if d > cohesion:
                cohesion = d
        # ------计算外离度------
        d1=[]
        d2=[]
        if preSamples is not None:
            for preSample in preSamples:
                d, a = AlgorithmUtil.cosinDistance(preSample, currentSample)
                d1.append(d)
        if nextSamples is not None:
            for nextSample in nextSamples:
                d, a = AlgorithmUtil.cosinDistance(nextSample, currentSample)
                d2.append(d)
        # 分别得到与两条子轨迹的不相似程度
        if len(d1)>0:
            d1=np.average(d1)
        else:
            d1=np.inf
        if len(d2)>0:
            d2=np.average(d2)
        else:
            d2=np.inf
        extrinsic = np.min([d1, d2])
        # 计算分数
        score = extrinsic - cohesion
        # 如果前后标签一致且都满足条件
        if isSame==True and d1<cohesion and d2<cohesion:
            preOrNext=-1
        else:
            preOrNext=np.argmin([d1, d2])
        return score,preOrNext
    # 计算单个轨迹点特征的轮廓系数(基于余弦距离)
    @staticmethod
    def __sihouetteCoefficient(feature,currentSequence,adjacentSequence):
        # 计算内聚度
        a_list=[]
        for i in currentSequence:
            if feature[0]==i[0] and feature[1]==i[1]:
                continue
            distance,angle=AlgorithmUtil.cosinDistance(feature,i)
            a_list.append(distance)
        if len(a_list)==0:
            a=0
        else:
            a=np.average(a_list)
        #计算外离度
        b_list=[]
        for j in adjacentSequence:
            distance,angle=AlgorithmUtil.cosinDistance(feature, j)
            b_list.append(distance)
        b=np.average(b_list)
        return (b-a)/np.max([a,b])
    # 轨迹粗划分
    @staticmethod
    def __roughDivision(trajectory):
        # 获取方向向量特征序列（list类型）
        vectorList,angleList=AlgorithmUtil.caculateVector(trajectory)
        # 获取聚类的合适k值
        k = FPTD_Kmeans.getKValue(angleList)
        # 向量序列转为numpy对象
        featureList=np.array(vectorList)
        # 获取类簇标签序列和聚类中心
        featureLabels, error, nfound = kcluster(data=vectorList, nclusters=k, dist='u',npass=50)
        #样本按标签分组的结果
        groupedSamples = {}
        # 获得每一个标签下的所有样本
        for label in np.unique(featureLabels):
            groupedSamples[label] = featureList[featureLabels == label]
        # 特征列表格式转换
        featureList=featureList.tolist()
        #潜在的轨迹分段位置索引序列
        potentialIndexList = FPTD_Kmeans.getPotentialSegmentIndex(featureLabels)
        # 分段的特征序列
        splitFeatureList=[]
        # 初始化轨迹分段结果（得到最开始的分段结果)
        for index, splitedIndex in enumerate(potentialIndexList):
            # 第一段轨迹
            if index == 0:
                currentFeatureList = featureList[0:potentialIndexList[index] + 1]
                splitFeatureList.append(currentFeatureList)
            # 最后一段轨迹
            if index == len(potentialIndexList) - 1:
                currentFeatureList = featureList[potentialIndexList[index] + 1:]
                splitFeatureList.append(currentFeatureList)
            # 其他轨迹
            elif index != len(potentialIndexList) - 1:
                currentFeatureList = featureList[potentialIndexList[index] + 1:potentialIndexList[index + 1]+1]
                splitFeatureList.append(currentFeatureList)
        return splitFeatureList,featureLabels,featureList,groupedSamples
    # 子轨迹合并
    @staticmethod
    def __mergeSegments(splitFeatureList,clusterLabels,featureList,groupedSamples):
        # 标志循环结束的变量
        end=False
        # 标志循环中的索引位置
        i=0
        #遍历每一个子轨迹
        while end==False:
            # 已经遍历到最后一条子轨迹
            if i == len(splitFeatureList)-1:
                end=True
            # 对长度为1的子轨迹判断是否需要合并
            if len(splitFeatureList[i])==1:
                # 获取子轨迹中的唯一轨迹段
                currentFeature=splitFeatureList[i][0]
                #获取该轨迹段的标签以及标签下的所有样本
                currentIndex=featureList.index(currentFeature)
                currentLabel=clusterLabels[currentIndex]
                currentSamples=groupedSamples[currentLabel]
                # 如果是第一条子轨迹
                if i==0:
                    # 获取下一条子轨迹
                    nextSamples=splitFeatureList[i+1]
                    # 计算分数
                    score,preOrNext =FPTD_Kmeans.__calculate_C_S2(currentSamples,currentFeature,None,nextSamples)
                # 如果是最后一条轨迹
                elif i==len(splitFeatureList)-1:
                    # 获取上一条子轨迹
                    preSamples = splitFeatureList[i - 1]
                    # 计算分数
                    score,preOrNext  = FPTD_Kmeans.__calculate_C_S2(currentSamples, currentFeature, preSamples, None)
                else:
                    # 获取上一条和下一条子轨迹
                    preSamples=splitFeatureList[i-1]
                    nextSamples = splitFeatureList[i + 1]
                    # 判断前后轨迹段的标签是否一致
                    preLabel=clusterLabels[currentIndex-1]
                    nextLabel=clusterLabels[currentIndex+1]
                    isSame=False
                    if preLabel==nextLabel:
                        isSame=True
                    # 计算分数
                    score,preOrNext = FPTD_Kmeans.__calculate_C_S2(currentSamples, currentFeature, preSamples, nextSamples,isSame)
                # 需要合并
                if score<=0:
                    # 和前一个子轨迹合并
                    if preOrNext==0:
                        # 当前子轨迹段中的首轨迹段移动至相邻轨迹段
                        splitFeatureList[i - 1].append(splitFeatureList[i].pop(0))
                        # 把空的子轨迹删除，索引不动
                        splitFeatureList.pop(i)
                    # 和后一个子轨迹合并
                    elif preOrNext==1:
                        # 当前子轨迹中的末轨迹段移动至相邻子轨迹
                        splitFeatureList[i + 1].insert(0, splitFeatureList[i].pop(-1))
                        # 把空的子轨迹删除，索引不动
                        splitFeatureList.pop(i)
                    # 与前后子轨迹一起合并（统一向前合并）
                    elif preOrNext==-1:
                        # 当前子轨迹中的首轨迹段移动至相邻轨迹段
                        splitFeatureList[i - 1].append(splitFeatureList[i].pop(0))
                        # 下一个子轨迹中所有轨迹段移动至前一个子轨迹中
                        for j in range(len(splitFeatureList[i+1])):
                            splitFeatureList[i-1].append(splitFeatureList[i+1].pop(0))
                        # 把空的子轨迹删除，索引不动
                        splitFeatureList.pop(i)
                        splitFeatureList.pop(i)
                        if i>len(splitFeatureList)-1:
                            break
                # 不需要合并
                else:
                    # 索引后移
                    i = i + 1
            else:
                # 索引后移
                i=i+1
        return splitFeatureList
    # 轨迹细划分
    @staticmethod
    def __fineDivision(splitFeatureList,featureLabels,featureList,groupedSamples):
         # 循环结束的标志
        end=False
        # 标识上一子轨迹是否调整了边界
        preChange = False
        # 判断是否需要提前跳出循环
        isbreak=False
        # 循环中的索引
        index=0
        while end==False:
            # 当前已经遍历到最后一条子轨迹
            if index == len(splitFeatureList)-1:
                end=True
            # 标识当前子轨迹是否被合并，以及是否检查过合并
            isMerge=False
            isCheckMerge=False
            # 如果当前子轨迹长度为1，直接跳过
            if len(splitFeatureList[index])==1:
                index=index+1
                continue
            # 如果不是第一段子轨迹
            if index > 0 and not preChange:
                while True:
                    # 保证每个子轨迹中的轨迹段至少为1
                    if (len(splitFeatureList[index]) == 1):
                        # 获取当前唯一轨迹段
                        currentFeature = splitFeatureList[index][0]
                        # 获取当前轨迹段在整条轨迹中所处的位置
                        currentFeatureIndex = featureList.index(currentFeature)
                        # 获取该轨迹段对应标签下的所有轨迹段
                        clusterSamples = groupedSamples[featureLabels[currentFeatureIndex]]
                        isSame = False
                        # 获取相邻的子轨迹
                        if index == len(splitFeatureList)-1:
                            nextSamples = None
                            preSamples = splitFeatureList[index - 1]
                        else:
                            preSamples = splitFeatureList[index - 1]
                            nextSamples = splitFeatureList[index + 1]
                            # 获取相邻轨迹段的标签
                            preLabel=featureLabels[currentFeatureIndex-1]
                            nextLabel=featureLabels[currentFeatureIndex+1]
                            if preLabel==nextLabel:
                                isSame=True
                        # 判断是否需要合并该轨迹段
                        score, preOrNext =FPTD_Kmeans.__calculate_C_S2(clusterSamples, currentFeature, preSamples, nextSamples,isSame)
                        # 需要合并
                        if score <= 0:
                            # 和前一个子轨迹合并
                            if preOrNext == 0:
                                # 当前子轨迹段中的首轨迹段移动至相邻轨迹段
                                splitFeatureList[index - 1].append(splitFeatureList[index].pop(0))
                                #删除空子轨迹
                                splitFeatureList.pop(index)
                            # 和后一个子轨迹合并
                            elif preOrNext == 1:
                                # 当前子轨迹中的末轨迹段移动至相邻子轨迹
                                splitFeatureList[index + 1].insert(0, splitFeatureList[index].pop(-1))
                                # 删除空子轨迹
                                splitFeatureList.pop(index)
                            elif preOrNext==-1:
                                # 当前子轨迹段中的首轨迹段移动至相邻轨迹段
                                splitFeatureList[index - 1].append(splitFeatureList[index].pop(0))
                                for j in range(len(splitFeatureList[index+1])):
                                    splitFeatureList[index - 1].append(splitFeatureList[index+1].pop(0))
                                # 删除空子轨迹
                                splitFeatureList.pop(index)
                                # 删除空子轨迹
                                splitFeatureList.pop(index)
                                # 跳出所有循环
                                if index>len(splitFeatureList)-1:
                                    isbreak=True
                            isMerge=True
                        isCheckMerge=True
                        break
                    # 获取该子轨迹的首个轨迹段
                    firstFeature = splitFeatureList[index][0]
                    # 计算这个轨迹段的轮廓系数，判断是否需要移动分段边界
                    sc = FPTD_Kmeans.__sihouetteCoefficient(firstFeature, splitFeatureList[index], splitFeatureList[index - 1])
                    # 需要对边界进行调整
                    if sc < 0:
                        # 当前子轨迹段中的首轨迹段移动至相邻轨迹段
                        splitFeatureList[index - 1].append(splitFeatureList[index].pop(0))
                    else:
                        break
            flag = False
            # 如果不是最后一段子轨迹，且没有被验证过合并条件
            if index<len(splitFeatureList)-1 and isCheckMerge==False:
                while True:
                    # 保证每个子轨迹中的轨迹段至少为1
                    if(len(splitFeatureList[index])==1):
                        # 获取当前唯一轨迹段
                        currentFeature = splitFeatureList[index][0]
                        # 获取当前轨迹段在整条轨迹中所处的位置
                        currentFeatureIndex = featureList.index(currentFeature)
                        # 获取该轨迹段对应标签下的所有轨迹段
                        clusterSamples = groupedSamples[featureLabels[currentFeatureIndex]]
                        isSame = False
                        # 获取相邻的子轨迹
                        if index == 0:
                            preSamples = None
                            nextSamples = splitFeatureList[index + 1]
                        else:
                            preSamples = splitFeatureList[index - 1]
                            nextSamples = splitFeatureList[index + 1]
                            # 获取相邻轨迹段的标签
                            preLabel = featureLabels[currentFeatureIndex - 1]
                            nextLabel = featureLabels[currentFeatureIndex + 1]
                            if preLabel == nextLabel:
                                isSame = True
                        # 判断是否需要合并该轨迹段
                        score,preOrNext = FPTD_Kmeans.__calculate_C_S2(clusterSamples, currentFeature, preSamples, nextSamples,isSame)
                        # 需要合并
                        if score <= 0:
                            # 和前一个子轨迹合并
                            if preOrNext == 0:
                                # 当前子轨迹段中的首轨迹段移动至相邻轨迹段
                                splitFeatureList[index - 1].append(splitFeatureList[index].pop(0))
                                # 删除空子轨迹
                                splitFeatureList.pop(index)
                            # 和后一个子轨迹合并
                            elif preOrNext == 1:
                                # 当前子轨迹中的末轨迹段移动至相邻子轨迹
                                splitFeatureList[index + 1].insert(0, splitFeatureList[index].pop(-1))
                                # 删除空子轨迹
                                splitFeatureList.pop(index)
                            elif preOrNext == -1:
                                # 当前子轨迹段中的首轨迹段移动至相邻轨迹段
                                splitFeatureList[index - 1].append(splitFeatureList[index].pop(0))
                                for j in range(len(splitFeatureList[index + 1])):
                                    splitFeatureList[index - 1].append(splitFeatureList[index + 1].pop(0))
                                # 删除空子轨迹
                                splitFeatureList.pop(index)
                                # 删除空子轨迹
                                splitFeatureList.pop(index)
                                # 跳出所有循环
                                if index > len(splitFeatureList) - 1:
                                    isbreak = True
                            isMerge = True
                        isCheckMerge = True
                        break
                    # 获取该子轨迹的末轨迹段
                    lastFeature=splitFeatureList[index][-1]
                    # 计算这个轨迹端的轮廓系数，判断是否需要移动分段边界
                    sc=FPTD_Kmeans.__sihouetteCoefficient(lastFeature,splitFeatureList[index],splitFeatureList[index+1])
                    # 需要对边界进行调整
                    if sc<0:
                        # 当前子轨迹中的末轨迹段移动至相邻子轨迹
                        splitFeatureList[index+1].insert(0,splitFeatureList[index].pop(-1))
                        # 只要调整过一次
                        flag=True
                    else:
                        break
            # 是否调整过
            preChange=flag
            # 需要跳出循环
            if isbreak:
                break
            # 如果子轨迹被合并，索引不动
            if isMerge:
                continue
            # 否则索引后移
            else:
                index=index+1

        resultSplitIndexList=[]
        sum=0
        for index,i in enumerate(splitFeatureList):
            # 如果当前是第一条子轨迹
            if index==0:
                sum=sum+len(i)-1
                resultSplitIndexList.append(sum)
            # 如果当前是最后一条子轨迹
            elif index==len(splitFeatureList)-1:
                break
            # 当前是其他子轨迹
            else:
                sum=sum+len(i)
                resultSplitIndexList.append(sum)
        return list(np.array(resultSplitIndexList)+1)
    # 算法执行
    def run(self):
        # -------------------轨迹粗划分---------------------------
        splitFeatureList,featureLabels,featureList,groupedSamples=FPTD_Kmeans.__roughDivision(self.trajectory)
        # -------------------子轨迹合并---------------------------
        splitFeatureList=FPTD_Kmeans.__mergeSegments(splitFeatureList,featureLabels,featureList,groupedSamples)
        # -------------------轨迹细划分---------------------------
        splitDirectionIndexList=FPTD_Kmeans.__fineDivision(splitFeatureList,featureLabels,featureList,groupedSamples)
        # 获取轨迹头尾的索引
        splitDirectionIndexList.insert(0,0)
        splitDirectionIndexList.append(len(self.trajectory)-1)
        # 提取指定索引位置的轨迹点
        compressTrajectory=[self.trajectory[index] for index in splitDirectionIndexList]
        return compressTrajectory

if __name__=='__main__':
    # 轨迹数据
    trajectory=[[32,3],[67,8],[2,6],[9,22],[5,34],[78,43],[89,23],[15,16]]
    # 创建压缩算法对象
    fptd=FPTD_Kmeans(trajectory)
    # 执行算法
    startTime=time.time()
    compressTrajectory=fptd.run()
    print(compressTrajectory)
    endTime=time.time()
    print(endTime-startTime)